1042D - Petya and Array - CodeForces Solution

//      بسم الله الرحمن الرحيم
//      All praise is due to ALLAH alone
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define go continue
#define exit return 0
#define ll long long int
#define ull unsigned long long int
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define print_vec(vec) for(int i=0;i<vec.size();i++)cout<<vec[i]<<' ';
#define print_set(st) for(auto it=st.begin();it!=st.end();it++)cout<<*it<<' ';
#define print_pair(vec) for(int i=0;i<vec.size();i++)cout<<vec[i].first<<' '<<vec[i].second<<endl;
#define dbg(num) cerr<< "Line "<<__LINE__ <<": "<< #num <<" = "<<(num)<<endl
//int dx[]={-2, -2, -1, -1,  1,  1,  2,  2};
//int dy[]={-1,  1, -2,  2, -2,  2, -1,  1};
int dx[] = { -1, 0, +1, 0};
int dy[] = {0, +1, 0, -1};
#define mod 1000000007
#define sz 200000
ll arr[sz + 1];
vector<ll>tree[sz * 4 + 4];
void build(int tree_index, int tree_start, int tree_end)
{
	if (tree_start == tree_end)
	{
		tree[tree_index].push_back(arr[tree_start]);
		return;
	}
	int mid = (tree_start + tree_end) / 2;
	build(tree_index * 2, tree_start, mid);
	build(tree_index * 2 + 1, mid + 1, tree_end);
	int i = 0, j = 0;
	while (i < tree[tree_index * 2].size() and j < tree[tree_index * 2 + 1].size())
	{
		ll a = tree[tree_index * 2][i];
		ll b = tree[tree_index * 2 + 1][j];
		if (a <= b)
			tree[tree_index].push_back(a), i++;
		else tree[tree_index].push_back(b), j++;
	}
	while (i < tree[tree_index * 2].size())
		tree[tree_index].push_back(tree[tree_index * 2][i]), i++;
	while (j < tree[tree_index * 2 + 1].size())
		tree[tree_index].push_back(tree[tree_index * 2 + 1][j]), j++;
}
int query(int tree_index, int tree_start, int tree_end, int l, int r, ll val)
{
	if (tree_start > r or tree_end < l)
		return 0;
	if (tree_start >= l and tree_end <= r)
	{
		int pos = lower_bound(tree[tree_index].begin(), tree[tree_index].end(), val) - tree[tree_index].begin();
		return pos;
	}
	int mid = (tree_start + tree_end) / 2;
	int left = query(tree_index * 2, tree_start, mid, l, r, val);
	int right = query(tree_index * 2 + 1, mid + 1, tree_end, l, r, val);
	return left + right;
}
int main()
{
	fast;
	ll n, t;
	cin >> n >> t;
	for (int i = 1; i <= n; i++)
	{
		ll a;
		cin >> a;
		if (i == 1)
			arr[i] = a;
		else arr[i] = arr[i - 1] + a;
	}
	build(1, 1, n);
	ll ans = 0;
	ans += query(1, 1, n, 1, n, t);
	for (int i = 1; i < n; i++)
	{
		ll cost = arr[i] + t;
		ans += query(1, 1, n, i + 1, n, cost);
	}
	cout << ans << endl;
//.............................................. ٱلْحَمْدُ لِلَّٰ......................................
}